//https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
package codeRandomThoughts.Test108将有序数组转换为二叉搜索树;

import codeRandomThoughts.utils.TreeNode;

public class Solution2 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    //左闭右闭
    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        //递归终止条件
        if (left > right) return null;
        if (left == right) return new TreeNode(nums[left]);

        //单层递归逻辑
        //构造根节点
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }
}
